package com.ztom.top100;

/**
 * 二叉树中的最大路径和
 * <p>
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
 *
 * @author ZhangTao
 */
public class Code46MaxPathSum {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int[] max = {Integer.MIN_VALUE};
        process(root, max);
        return max[0];
    }

    private int process(TreeNode node, int[] max) {
        if (node == null) {
            return 0;
        }

        int lMax = Math.max(process(node.left, max), 0);
        int rMax = Math.max(process(node.right, max), 0);

        max[0] = Math.max(max[0], lMax + rMax + node.val);

        return node.val + Math.max(lMax, rMax);
    }
}
